home *** CD-ROM | disk | FTP | other *** search
/ Die Ultimative Software-P…i Collection 1996 & 1997 / Die Ultimative Software-Pakete CD-ROM fur Atari Collection 1996 & 1997.iso / g / gnu_c / gpplib22.zoo / libsrc / xfix.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-12  |  12.5 KB  |  614 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3. Copyright (C) 1989 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18. //
  19. // Fix.cc : variable length fixed point data type class functions
  20. //
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <xfix.h>
  26. #include <std.h>
  27. #include <xobstack.h>
  28. #include <xallocri.h>
  29. #include <strstream.h>
  30.  
  31. // default parameters
  32.  
  33. uint16 Fix_default_length = 16;
  34. int    Fix_default_print_width = 8;
  35.  
  36. Fix_peh Fix_overflow_handler = Fix_overflow_saturate;
  37.  
  38. _Frep _Frep_0    = { 16, 1, 1, { 0 } };
  39. _Frep _Frep_m1    = { 16, 1, 1, { 0x8000 } };
  40. _Frep _Frep_quotient_bump = { 16, 1, 1, { 0x4000 } };
  41.  
  42. // error handling
  43.  
  44. void default_Fix_error_handler(const char* msg)
  45. {
  46.   cerr << "Fix: " << msg << "\n";
  47.   abort();
  48. }
  49.  
  50. void default_Fix_range_error_handler(const char* msg)
  51. {
  52.   cerr << "Fix: range error in " << msg << "\n";
  53.   //abort();
  54. }
  55.  
  56. one_arg_error_handler_t 
  57.   Fix_error_handler = default_Fix_error_handler,
  58.   Fix_range_error_handler = default_Fix_range_error_handler;
  59.  
  60. one_arg_error_handler_t set_Fix_error_handler(one_arg_error_handler_t f)
  61. {
  62.   one_arg_error_handler_t old = Fix_error_handler;
  63.   Fix_error_handler = f;
  64.   return old;
  65. }
  66.  
  67. one_arg_error_handler_t set_Fix_range_error_handler(one_arg_error_handler_t f)
  68. {
  69.   one_arg_error_handler_t old = Fix_range_error_handler;
  70.   Fix_range_error_handler = f;
  71.   return old;
  72. }
  73.  
  74. void Fix::error(const char* msg)
  75. {
  76.   (*Fix_error_handler)(msg);
  77. }
  78.  
  79. void Fix::range_error(const char* msg)
  80. {
  81.   (*Fix_range_error_handler)(msg);
  82. }
  83.  
  84. // _Frep allocation and initialization functions
  85.  
  86. static inline _Fix _new_Fix(uint16 len)
  87. {
  88.   int siz = (((uint32 )len + 15) >> 4);
  89.   if (siz <= 0) siz = 1;
  90.   size_t allocsiz = (sizeof(_Frep) + (siz - 1) * sizeof(uint16));
  91.   _Fix z = (_Fix)(new char[allocsiz]);
  92.   memset(z, 0, allocsiz);
  93.   z->len = len;
  94.   z->siz = siz;
  95.   z->ref = 1;
  96.   return z;
  97. }
  98.  
  99. _Fix new_Fix(uint16 len)
  100. {
  101.   return _new_Fix(len);
  102. }
  103.  
  104. _Fix new_Fix(uint16 len, const _Fix x)
  105. {
  106.   _Fix z = _new_Fix(len);
  107.   return copy(x,z);
  108. }
  109.  
  110. _Fix new_Fix(uint16 len, double d)
  111. {
  112.   _Fix z = _new_Fix(len);
  113.  
  114.   if ( d == _Fix_max_value )
  115.   {
  116.     z->s[0] = 0x7fff;
  117.     for ( int i=1; i < z->siz; i++ )
  118.       z->s[i] = 0xffff;
  119.   }
  120.   else if ( d < _Fix_min_value || d > _Fix_max_value )
  121.     (*Fix_range_error_handler)("declaration");
  122.   else
  123.   {
  124.     if (d < 0)
  125.       d += 2.0;
  126.     d *= 32768;
  127.     for ( int i=0; i < z->siz; i++ )
  128.     {
  129.       z->s[i] = (uint16 )d;
  130.       d -= z->s[i];
  131.       d *= 65536;
  132.     }
  133.     if ( d >= 32768 )
  134.       z->s[z->siz-1]++;
  135.   }
  136.   mask(z);
  137.   return z;
  138. }
  139.  
  140. // convert to a double 
  141.  
  142. double value(const Fix& x)
  143. { 
  144.   double d = 0.0;
  145.   for ( int i=x.rep->siz-1; i >= 0; i-- )
  146.   {
  147.     d += x.rep->s[i];
  148.     d *= 1./65536.;
  149.   }
  150.   d *= 2.;
  151.   return d < 1. ? d : d - 2.;
  152. }
  153.  
  154. // extract mantissa to Integer
  155.  
  156. Integer mantissa(Fix& x)
  157. {
  158.   Integer a = 1, b=1;
  159.   for ( int i=0; i < x.rep->siz; i++ )
  160.   {
  161.     a <<= 16;
  162.     a += x.rep->s[i];
  163.     b <<= 16;
  164.   }
  165.   return a-b;
  166. }
  167.  
  168. // comparison functions
  169.   
  170. inline static int docmp(uint16* x, uint16* y, int siz)
  171. {
  172.   int diff = (int16 )*x - (int16 )*y;
  173.   while ( --siz && !diff )
  174.     diff = (int32 )(uint32 )*++x - (int32 )(uint32 )*++y;
  175.   return diff;
  176. }
  177.  
  178. inline static int docmpz(uint16* x, int siz)
  179. {
  180.   while ( siz-- )
  181.     if ( *x++ ) return 1;
  182.   return 0;
  183. }
  184.  
  185. int compare(const _Fix x, const _Fix y)
  186. {
  187.   if ( x->siz == y->siz )
  188.     return docmp(x->s, y->s, x->siz);
  189.   else
  190.   {
  191.     int r;
  192.     _Fix longer, shorter;
  193.     if ( x->siz > y->siz )
  194.     {
  195.       longer = x;
  196.       shorter = y;
  197.       r = 1;
  198.     }
  199.     else
  200.     {
  201.       longer = y;
  202.       shorter = x;
  203.       r = -1;
  204.     }
  205.     int diff = docmp(x->s, y->s, shorter->siz);
  206.     if ( diff )
  207.       return diff;
  208.     else if ( docmpz(&longer->s[shorter->siz], longer->siz-shorter->siz) )
  209.       return r;
  210.     else
  211.       return 0;
  212.   }
  213. }
  214.  
  215. // arithmetic functions
  216.  
  217. _Fix add(_Fix x, _Fix y, _Fix r)
  218. {
  219.   uint16 xsign = x->s[0], ysign = y->s[0];
  220.   _Fix longer, shorter;
  221.   if ( x->len >= y->len )
  222.     longer = x, shorter = y;
  223.   else
  224.     longer = y, shorter = x;
  225.   if ( r == NULL )
  226.     r = new_Fix(longer->len);
  227.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  228.     r->s[i] = 0;
  229.   for ( ; i >= shorter->siz; i-- )
  230.     r->s[i] = longer->s[i];
  231.   uint32 sum = 0, carry = 0;
  232.   for ( ; i >= 0; i-- )
  233.   {
  234.     sum = carry + (uint32 )x->s[i] + (uint32 )y->s[i];
  235.     carry = sum >> 16;
  236.     r->s[i] = sum;
  237.   }
  238.   if ( (xsign ^ sum) & (ysign ^ sum) & 0x8000 )
  239.     (*Fix_overflow_handler)(r);
  240.   return r;
  241. }
  242.  
  243. _Fix subtract(_Fix x, _Fix y, _Fix r)
  244. {
  245.   uint16 xsign = x->s[0], ysign = y->s[0];
  246.   _Fix longer, shorter;
  247.   if ( x->len >= y->len )
  248.     longer = x, shorter = y;
  249.   else
  250.     longer = y, shorter = x;
  251.   if ( r == NULL )
  252.     r = new_Fix(longer->len);
  253.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  254.     r->s[i] = 0;
  255.   for ( ; i >= shorter->siz; i-- )
  256.     r->s[i] = (longer == x ? x->s[i] : -y->s[i]);
  257.   int16 carry = 0;
  258.   uint32 sum = 0;
  259.   for ( ; i >= 0; i-- )
  260.   {
  261.     sum = (int32 )carry + (uint32 )x->s[i] - (uint32 )y->s[i];
  262.     carry = sum >> 16;
  263.     r->s[i] = sum;
  264.   }
  265.   if ( (xsign ^ sum) & (~ysign ^ sum) & 0x8000 )
  266.     (*Fix_overflow_handler)(r);
  267.   return r;
  268. }
  269.  
  270. _Fix multiply(_Fix x, _Fix y, _Fix r)
  271. {
  272.   if ( r == NULL )
  273.     r = new_Fix(x->len + y->len);
  274.   int xsign = x->s[0] & 0x8000,
  275.     ysign = y->s[0] & 0x8000;
  276.   Fix X(x->len), Y(y->len);
  277.   if ( xsign )
  278.     x = negate(x,X.rep);
  279.   if ( ysign )
  280.     y = negate(y,Y.rep);
  281.   for ( int i=0; i < r->siz; i++ )
  282.     r->s[i] = 0;
  283.   for ( i=x->siz-1; i >= 0; i-- )
  284.   {
  285.     uint32 carry = 0;
  286.     for ( int j=y->siz-1; j >= 0; j-- ) 
  287.     {
  288.       int k = i + j + 1;
  289.       uint32 a = (uint32 )x->s[i] * (uint32 )y->s[j];
  290.       uint32 b = ((a << 1) & 0xffff) + carry;
  291.       if ( k < r->siz )
  292.       {
  293.     b += r->s[k];
  294.         r->s[k] = b;
  295.       }
  296.       if ( k < (int)r->siz + 1 )
  297.         carry = (a >> 15) + (b >> 16);
  298.     }
  299.     r->s[i] = carry;
  300.   }
  301.   if ( xsign != ysign )
  302.     negate(r,r);
  303.   return r;
  304. }
  305.  
  306. _Fix multiply(_Fix x, int y, _Fix r)
  307. {
  308.   if ( y != (int16 )y )
  309.     (*Fix_range_error_handler)("multiply by int -- int too large");
  310.   if ( r == NULL )
  311.     r = new_Fix(x->len);
  312.   for ( int i=r->siz-1; i >= x->siz; i-- )
  313.     r->s[i] = 0;
  314.   int32 a, carry = 0;
  315.   for ( ; i > 0; i-- )
  316.   {
  317.     a = (int32 )(uint32 )x->s[i] * y + carry;
  318.     r->s[i] = a;
  319.     carry = a >> 16;        // assumes arithmetic right shift
  320.   }
  321.   a = (int32 )(int16 )x->s[0] * y + carry;
  322.   r->s[0] = a;
  323.   a &= 0xffff8000L;
  324.   if ( a != 0xffff8000L && a != 0L ) {
  325.     r->s[0] = 0x8000 ^ x->s[0] ^ y;
  326.     (*Fix_overflow_handler)(r);
  327.   }
  328.   return r;
  329. }
  330.  
  331. _Fix divide(_Fix x, _Fix y, _Fix q, _Fix r)
  332. {
  333.   int xsign = x->s[0] & 0x8000, 
  334.     ysign = y->s[0] & 0x8000;
  335.   if ( q == NULL )
  336.     q = new_Fix(x->len);
  337.   copy(&_Frep_0,q);
  338.   if ( r == NULL )
  339.     r = new_Fix(x->len + y->len - 1);
  340.   if ( xsign )
  341.     negate(x,r);
  342.   else
  343.     copy(x,r);
  344.   Fix Y(y->len);
  345.   y = ( ysign ? negate(y,Y.rep) : copy(y,Y.rep) );
  346.   if ( !compare(y) )
  347.     (*Fix_range_error_handler)("division -- division by zero");
  348.   else if ( compare(x,y) >= 0 )
  349.     if ( compare(x,y) == 0 && (xsign ^ ysign) != 0 )
  350.     {
  351.       copy(&_Frep_m1,q);
  352.       copy(&_Frep_0,r);
  353.     }
  354.     else
  355.       (*Fix_range_error_handler)("division");
  356.   else
  357.   {
  358.     _Fix t;
  359.     Fix S(r->len),
  360.       W(q->len,&_Frep_quotient_bump);
  361.     for ( int i=1; i < q->len; i++ )
  362.     {
  363.       shift(y,-1,y);
  364.       subtract(r,y,S.rep);
  365.       int s_status = compare(S.rep);
  366.       if ( s_status == 0 ) 
  367.       {
  368.     t = r, r = S.rep, S.rep = t;
  369.     break;
  370.       }
  371.       else if ( s_status > 0 )
  372.       {
  373.     t = r, r = S.rep, S.rep = t;
  374.     add(q,W.rep,q);
  375.       }
  376.       shift(W.rep,-1,W.rep);
  377.     }
  378.     if ( xsign ^ ysign )
  379.       negate(q,q);
  380.   }
  381.   return q;
  382. }
  383.  
  384. _Fix shift(_Fix x, int y, _Fix r)
  385. {
  386.   if ( y == 0 )
  387.     return x;
  388.   else if ( r == NULL )
  389.     r = new_Fix(x->len);
  390.  
  391.   int ay = abs((long) y),
  392.     ayh = ay >> 4,
  393.     ayl = ay & 0x0f;
  394.   int xl, u, ilow, ihigh;
  395.   uint16 *rs, *xsl, *xsr;
  396.  
  397.   if ( y > 0 )
  398.   {
  399.     rs = r->s;
  400.     xsl = x->s + ayh;
  401.     xsr = xsl + 1;
  402.     xl = ayl;
  403.     u = 1;
  404.     ihigh = x->siz - ayh - 1;
  405.     ilow = 0;
  406.   }
  407.   else
  408.   {
  409.     rs = &r->s[r->siz - 1];
  410.     xsr = &x->s[r->siz - 1] - ayh;
  411.     xsl = xsr - 1;
  412.     xl = 16 - ayl;
  413.     u = -1;
  414.     ihigh = r->siz - ayh - 1;
  415.     ilow = ihigh - x->siz;
  416.   }
  417.  
  418.   int xr = 16 - xl;
  419.   uint16 xrmask = 0xffffL >> xr;
  420.   for ( int i=0; i < ilow; i++, rs+=u, xsl+=u, xsr+=u )
  421.     *rs = 0;
  422.   for ( ; i < ihigh; i++, rs+=u, xsl+=u, xsr+=u )
  423.     *rs = (*xsl << xl) + ((*xsr >> xr) & xrmask);
  424.   *rs = (y > 0 ? (*xsl << xl) : ((*xsr >> xr) & xrmask));
  425.   rs += u;
  426.   for ( ; ++i < r->siz; rs+=u )
  427.     *rs = 0;
  428.   return r;
  429. }
  430.  
  431. _Fix negate(_Fix x, _Fix r)
  432. {
  433.   if ( r == NULL )
  434.     r = new_Fix(x->len);
  435.   uint32 carry = 1;
  436.   for ( int i=r->siz-1; i >= x->siz; i-- )
  437.     r->s[i] = 0;
  438.   for ( ; i >= 0; i-- )
  439.   {
  440.     uint32 a = (uint16 )~x->s[i] + carry;    // bug work-around
  441.     r->s[i] = a;
  442.     carry = a >> 16;
  443.   }
  444.   return r;
  445. }
  446.  
  447. // io functions
  448.  
  449. Fix atoF(const char* a, int len)
  450. {
  451.   return Fix(len,atof(a));
  452. }
  453.  
  454. extern AllocRing _libgxx_fmtq;
  455.  
  456. void Fix::printon(ostream& s, int width) const
  457. {
  458.   double val = value(*this);
  459.   int old_precision = s.precision(width-3);
  460.   long old_flags = s.setf(ios::fixed, ios::fixed|ios::scientific);
  461.   if (val >= 0)
  462.       s << ' ';
  463.   s.width(width-2);
  464.   s << val;
  465.   s.precision(old_precision);
  466.   s.flags(old_flags);
  467. }
  468.  
  469. char* Ftoa(Fix& x, int width)
  470. {
  471.   int wrksiz = width + 2;
  472.   char *fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  473.   ostrstream stream(fmtbase, wrksiz);
  474.   
  475.   x.printon(stream, width);
  476.   stream << ends;
  477.   return fmtbase;
  478. }
  479.  
  480. extern Obstack _libgxx_io_ob;
  481.  
  482. Fix Fix::operator %= (int y)
  483. {
  484.   Fix r((int )rep->len + y, *this); return *this = r;
  485. }
  486.  
  487. istream& operator >> (istream& s, Fix& y)
  488. {
  489.   int got_one = 0;
  490.   if (!s.ipfx(0))
  491.   {
  492.     s.clear(ios::failbit|s.rdstate()); // Redundant if using GNU iostreams.
  493.     return s;
  494.   }
  495.  
  496.   char sign = 0, point = 0;
  497.   char ch;
  498.   s >> ws;
  499.   if (!s.good())
  500.   {
  501.     s.clear(ios::failbit|s.rdstate());
  502.     return s;
  503.   }
  504.   while (s.get(ch))
  505.   {
  506.     if (ch == '-')
  507.     {
  508.       if (sign == 0)
  509.       {
  510.         sign = 1;
  511.         _libgxx_io_ob.grow(ch);
  512.       }
  513.       else
  514.         break;
  515.     }
  516.     if (ch == '.')
  517.     {
  518.       if (point == 0)
  519.       {
  520.         point = 1;
  521.         _libgxx_io_ob.grow(ch);
  522.       }
  523.       else
  524.         break;
  525.     }
  526.     else if (ch >= '0' && ch <= '9')
  527.     {
  528.       got_one = 1;
  529.       _libgxx_io_ob.grow(ch);
  530.     }
  531.     else
  532.       break;
  533.   }
  534.   char * p = (char*)(_libgxx_io_ob.finish(0));
  535.   if (s.good())
  536.     s.putback(ch);
  537.   if (!got_one)
  538.     s.clear(ios::failbit|s.rdstate());
  539.   else
  540.     y = atoF(p);
  541.   _libgxx_io_ob.free(p);
  542.   return s;
  543. }
  544.  
  545. void show(Fix& x)
  546. {
  547.   cout << "len = " << x.rep->len << "\n";
  548.   cout << "siz = " << x.rep->siz << "\n";
  549.   cout << "ref = " << x.rep->ref << "\n";
  550.   cout << "man = ";
  551. #ifdef _OLD_STREAMS
  552.   cout << Itoa(mantissa(x),16,4*x.rep->siz);
  553. #else
  554.   int old_flags = cout.setf(ios::hex, ios::hex|ios::dec|ios::oct);
  555.   cout.width(4*x.rep->siz);
  556.   cout << mantissa(x);
  557.   cout.setf(old_flags, ios::hex|ios::dec|ios::oct);
  558. #endif
  559.   cout << "\n";
  560.   cout << "val = " << value(x) << "\n";
  561. }
  562.  
  563. // parameter setting operations
  564.  
  565. Fix_peh set_overflow_handler(Fix_peh new_handler) {
  566.   Fix_peh old_handler = Fix_overflow_handler;
  567.   Fix_overflow_handler = new_handler;
  568.   return old_handler;
  569. }
  570.  
  571. int Fix_set_default_length(int newlen)
  572. {
  573.   uint16 oldlen = Fix_default_length;
  574.   if ( newlen < _Fix_min_length || newlen > _Fix_max_length )
  575.     (*Fix_error_handler)("illegal length in Fix_set_default_length");
  576.   Fix_default_length = newlen;
  577.   return oldlen;
  578. }
  579.  
  580. // overflow handlers
  581.  
  582. void Fix_overflow_saturate(_Fix& r) {
  583.   if ( (int16 )r->s[0] > 0 ) 
  584.   {
  585.     r->s[0] = 0x8000;
  586.     for ( int i=1; i < r->siz; i++ )
  587.       r->s[i] = 0;
  588.   }
  589.   else
  590.   {
  591.     r->s[0] = 0x7fff;
  592.     for ( int i = 1; i < (int)r->siz; i++ )
  593.       r->s[i] = 0xffff;
  594.     mask(r);
  595.   }
  596. }
  597.  
  598. void Fix_overflow_wrap(_Fix&) {}
  599.  
  600. void Fix_overflow_warning_saturate(_Fix& r) {
  601.   Fix_overflow_warning(r);
  602.   Fix_overflow_saturate(r);
  603. }
  604.  
  605. void Fix_overflow_warning(_Fix&) {
  606.   cerr << "Fix: overflow warning\n"; 
  607. }
  608.  
  609. void Fix_overflow_error(_Fix&) {
  610.   cerr << "Fix: overflow error\n"; 
  611.   abort();
  612. }
  613.  
  614.